package 二分查找.easy;

/**
 * 1. 问题描述
 *      你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
 *      由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
 *      假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 *      你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。
 *      实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 *
 * 2. 算法分析
 *      1. 二分法(比较典型) logn
 *      2. 双指针
 *      3. 线性扫描(不推荐，需要频繁的调用api isBadVersion()) n
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 第一个错误的版本 {
    public static void main(String[] args) {

    }

    // leetcode官方给的二分 比较和官方写的区别（我自己写的二分也可以实现，但是效率没有官方的高????）
    public static int firstBadVersion2(int n) {
        int left = 1;
        int right = n;
        while (left < right) { // 为什么等于的情况给排除了?
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid; // 为什么不是 right = mid - 1?
            } else {
                left = mid + 1;
            }
        }
        return left;
    }


    // 二分法
    public static int firstBadVersion1(int n) {
        int i = 1; int j = n;
        int ans = 0;
        while(i <= j) {
            int mid = i + (j - i) / 2;
            if(isBadVersion(mid) == true) {
                ans = mid;
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return ans;
    }

    // 判断当前版本号是否错误
    public static boolean isBadVersion(int n) {
        return true;
    }
}
